/**
 * 给出一个二维整数网格grid，网格中的每个值表示该位置处的网格块的颜色。
 * 只有当两个网格块的颜色相同，而且在四个方向中任意一个方向上相邻时，它们属于同一连通分量。
 * 连通分量的边界是指连通分量中的所有与不在分量中的正方形相邻（四个方向上）的所有正方形，或者在网格的边界上（第一行/列或最后一行/列）的所有正方形。
 * 给出位于(r0, c0)的网格块和颜色color，使用指定颜色color为所给网格块的连通分量的边界进行着色，并返回最终的网格grid 。
 * <p>
 * 示例 1：
 * 输入：grid = [[1,1],[1,2]], r0 = 0, c0 = 0, color = 3
 * 输出：[[3, 3], [3, 2]]
 * <p>
 * 示例 2：
 * 输入：grid = [[1,2,2],[2,3,2]], r0 = 0, c0 = 1, color = 3
 * 输出：[[1, 3, 3], [2, 3, 3]]
 * <p>
 * 示例 3：
 * 输入：grid = [[1,1,1],[1,1,1],[1,1,1]], r0 = 1, c0 = 1, color = 2
 * 输出：[[2, 2, 2], [2, 1, 2], [2, 2, 2]]
 * <p>
 * 提示：
 * 1 <= grid.length <= 50
 * 1 <= grid[0].length <= 50
 * 1 <= grid[i][j] <= 1000
 * 0 <= r0 < grid.length
 * 0 <= c0 < grid[0].length
 * 1 <= color <= 1000
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/coloring-a-border
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Q01034m {

    private int m, n;

    private boolean[][] visited; // 标记数组

    public int[][] colorBorder(int[][] grid, int row, int col, int color) {
        visited = new boolean[grid.length][grid[0].length];
        m = grid.length - 1;
        n = grid[0].length - 1;
        dfs(grid, row, col, grid[row][col], color);
        return grid;
    }

    private void dfs(int[][] grid, int row, int col, int source, int target) {
        if (row < 0 || row > m || col < 0 || col > n || grid[row][col] != source || visited[row][col])
            return; // 是否越界或不是源色
        visited[row][col] = true;
        if (row == 0 || row == m || col == 0 || col == n ||
                (!visited[row - 1][col] && grid[row - 1][col] != source) ||
                (!visited[row + 1][col] && grid[row + 1][col] != source) ||
                (!visited[row][col - 1] && grid[row][col - 1] != source) ||
                (!visited[row][col + 1] && grid[row][col + 1] != source)) { // 边界或者相邻有没访问过，且不与source相等的
            grid[row][col] = target;
        }
        dfs(grid, row - 1, col, source, target);
        dfs(grid, row + 1, col, source, target);
        dfs(grid, row, col - 1, source, target);
        dfs(grid, row, col + 1, source, target);
    }
}
